1. Field of The Invention
This invention relates to a Viterbi decoding method of what is called a Trellis coding/Viterbi decoding method which is an error-correcting code method employed and specified in the CCITT (Comite Consultatif International de Telephone et Telegraph) recommendation V. 33 as a primary technique.
2. Description of The Related Art
Many studies of error correcting codes have been made since twenty or thirty years ago. Such studies take their origin from the fact that in 1948, C. E. Shannon presented a paper disclosing the presence of an error correcting code, which can decrease an error rate after decoded, in a noisy channel. Among many error-correcting coding methods such as a block code method, a Trellis coding/Viterbi decoding method is known as a method which is most suitable for correcting random errors and can obtain a very efficient coding gain. This is a method for minimizing a current error by using information on the past in order to reduce noises due to closeness of a receiving point.
Next, the Trellis coding/Viterbi decoding method will be described hereinbelow by referring to the accompanying drawings.
FIG. 1 illustrates the configuration of what is called a Trellis encoder according to the present invention. First, data to be transmitted from a terminal is converted by a parallel conversion device into 6-bit parallel data words (namely, 6-bit units of information). Then, all six bits Q.sub.n6, Q.sub.n5, Q.sub.n4, Q.sub.n3, Q.sub.n2 and Q.sub.n1 of each of the parallel data words are simultaneously transmitted therefrom over separate wires and input to the Trellis encoder. In this Trellis encoder, two bits Q.sub.n2 and Q.sub.n1 input to a differential encoding portion (hereunder sometimes referred to simply as a differential encoder) undergo a differential coding and resultant data is subsequently input to a convolutional encoding portion (hereunder sometimes referred to simply as a convolutional encoder) as 2-bit data to be encoded (hereunder sometimes referred to as coding data), the bits of which are represented by Y.sub.n2 and Y.sub.n1, respectively. FIG. 2 is a diagram for illustrating a coding effected by the differential encoder. When the coding is effected, a redundant bit is added to the two bits Y.sub.n2 and Y.sub.n1 and 3-bit resultant coding data, the bits of which are represented by Y.sub.n2, Y.sub.n1 and Y.sub.n0, respectively, is obtained. The bits Q.sub.n6 to Q.sub.n3 are output from the Trellis encoder without any change. Consequently, the Trellis encoder outputs 7-bit data word comprised of the bits Q.sub.n6 to Q.sub.n3, Y.sub.n2, Y.sub.n1 and Y.sub.n0.
In the convolutional encoder of FIG. 1, three consecutive data bits W.sub.n3 , W.sub.n2 and W.sub.n1 represent 8 states. Furthermore, transitions from a state represented by W.sub.n3, W.sub.n2 and W.sub.n1 to four states represented by W.sub.n+1 3, W.sub.n+1 2 and W.sub.n+1 1 can occur. FIGS. 3 to 10 are state transition diagrams. FIG. 3 shows transitions from a state represented by the three bits 000 to four states respectively represented by 000, 010, 100 and 110. A set {000} described over a transition line drawn between the states represented by 000 indicates one of cases denoted by three consecutive data bits {Y.sub.n+1 2, Y.sub.n+1 1 and Y.sub.n+1 0 }. Each of eight cases represented by the three consecutive data bits {Y.sub.n2, Y.sub.n1 and Y.sub.n0 } is called a group. Namely, the eight cases represented by the three bits are called a 000-group (or a group 0 ) to a 111-group (or a group 7), respectively.
FIG. 11 is a signal space diagram showing 128 mapped signal points represented by 7-bit output data Q.sub.n6 .about.Q.sub.n3 Y.sub.n2 Y.sub.n1 Y.sub.n0 of the Trellis encoder in case effecting Trellis Coded Modulation (TCM) at 14,400 bits per second (bps). The horizontal axis represents a real (Re) axis; and the vertical axis an imaginary (Im) axis. In this figure, binary numbers are binary values indicated by the data Q.sub.n6 .about.Q.sub.n3 Y.sub.n2 Y.sub.n1 Y.sub.n0.
FIG. 12 is a schematic block diagram for illustrating the configuration of hardware of from the Trellis encoder 1 to a device for outputting an encoded signal to a circuit or line. The data Q.sub.n6 .about.Q.sub.n3 Y.sub.n2 Y.sub.n1 Y.sub.n0 output from the Trellis encoder 1 of FIG. 1 is developed by a mapping portion 2 to data representing a communication point (namely, a signal point) of FIG. 11. Subsequently, the resultant data is decomposed therein into a real part thereof (hereunder sometimes referred to as Re-axis data) and an imaginary part thereof (hereunder sometimes referred to as Im-axis data), each of which is then filtered by a corresponding low-pass filter 3. Thereafter, the filtered Re-axis data is multiplied by COS .omega. t in a corresponding multiplier 4. Similarly, the filtered Im-axis data is multiplied by SIN .omega. t in a corresponding multiplier 4. Results of these multiplications are added to each other in an adder 5. Finally, a signal representing a result of this addition is output from the adder 5 and is transmitted to the circuit or line as the encoded signal. This is what is called Quadrature Amplitude Modulation (QAM) system.
FIG. 13 is a schematic block diagram illustrating the configuration of hardware for receiving an input encoded signal from the circuit or line, then decoding data represented by the input signal by using of a Viterbi decoder 11 and outputting resultant data. First, transmitted data represented by the received encoded signal from the circuit or line is input to a multiplier 6, whereupon the transmitted data is multiplied by COS .omega. t to obtain Re-axis data. Further, the transmitted data is also input to another multiplier 6, whereupon the transmitted data is multiplied by SIN .omega. t to obtain Im-axis data. Then, each of the obtained Re-axis and Im-axis data is filtered by a corresponding low-pass filter 7. Subsequently, the filtered Re-axis and Im-axis data are input to an equalizer portion 8 whereupon a distortion is eliminated from each of the Re-axis and Im-axis data. Thereafter, the Re-axis and Im-axis data output from the portion 8 are input to a carrier automatic-phase-control (APC) device 9 to regulate the phase thereof. The data output from the device 9 and developed to a signal space 10 represented by using the Im-axis and Re-axis is shown in the lower right region of FIG. 13. Such received data is then decoded by the Viterbi decoder 11 to restore the original signal representing the data Q.sub.n6 .about. Q.sub.n3 Q.sub.n2 Q.sub.n1.
When decoding the received data in case of a 14,400-bps operation, the 128 signal points of FIG. 11 are searched for the transmitted signal point because the transmitted signal point should be one of the 128 signal points. It is, however, usual that data representing a point or position shifted from the signal point of FIG. 11 is transmitted due to a noise or distortion occurring during the transmission. Therefore, it should be estimated from a signal point indicated by the actually transmitted data (hereunder sometimes referred to as a reception signal point) what would be correct output data in case where no noise or distortion occurred during the transmission. Thus, a conventional method, which will be outlined hereinbelow, is performed in order to make such an estimation. First, the signal points of FIG. 11 represented by the data Q.sub.n6 .about.Q.sub.n3 Y.sub.n2 Y.sub.n1 Y.sub.n0 are classified into 8 groups according to or correspondingly to three consecutive bits Y.sub.n2 Y.sub.n1 Y.sub.n0, the binary value of each of which ranges from 000 to 111. Each signal point is positioned apart from other signal points. Thus, in each group of signal points, a signal point closest to the reception signal point is detected. Subsequently, it is determined which one of the detected signal points respectively corresponding to the eight groups is closest to the reception signal point. Then, the correct output data is estimated by further taking into account information on previous transmissions to minimize an estimation error.
FIG. 14 shows the distribution of the signal points of the eight groups of FIG. 11, in which character A represents a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =000; H a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =001; B a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =010; E a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =011; C a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =100; F a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =101; D a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =110; G a signal point corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =111; and subscripts 0 to 15 decimal values indicated by four consecutive bits Q.sub.n6 Q.sub.n5 Q.sub.n4 Q.sub.n3 (namely, each group consists of 16 signal points respectively corresponding to the subscripts 0 to 15).
FIGS. 15 to 22 correspond to the eight groups of the signal points, respectively (namely, these figures illustrate the distributions of the signal points of the eight groups, respectively). For instance, FIG. 15 illustrates 16 signal points, which are represented by characters 0.about.9, A, B, C, D, E and F of the group corresponding to a case that Y.sub.n2 Y.sub.n1 Y.sub.n0 =000.
As described above, the conventional method requires diagrams like FIGS. 15 to 22 respectively corresponding to the eight groups (or tables based on such diagrams). Further, in the prior art, a decoder is constituted only by hardware, and a decoding by software using macroinstructions has not been realized.
The present invention is accomplished to resolve the foregoing problems of the prior art.
It is an object of the present invention to provide a Viterbi decoding method suitable for performing a decoding by software, which can calculate data of the eight groups from data of one of the eight groups.